#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <cmath>
#include <algorithm>
using namespace std;
class Solution
{
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		
		if(0>=n && 0>=m)
			return 0;
		if(0>=n)
			return (m%2)?A[m/2]:((double(A[m/2])+double(A[m/2-1]))/2);
		if(0>=m)
			return (n%2)?B[n/2]:((double(B[n/2])+double(B[n/2-1]))/2);

		if(m==1)
			return this->getMediaBase1(A[0],B,n);
		else if(n==1)
			return this->getMediaBase1(B[0],A,m);

		if(m==2)
			return this->getMedianBase2(A,B,n);
		else if(n==2)
			return this->getMedianBase2(B,A,m);


		//when m>=2 && n>=2
		int amid = (m%2)?(m/2):(m/2-1);
		int bmid = (n%2)?(n/2):(n/2-1);
		int k;

		if(A[amid] > B[bmid])
		{
			k = (m%2)?min(amid,bmid):min(amid,bmid+1);
			return findMedianSortedArrays(A,m-k,B+k,n-k);
		}
		else
		{
			k = (n%2)?min(amid,bmid):min(amid+1,bmid);
			return findMedianSortedArrays(A+k,m-k,B,n-k);
		}
	}

	double getMediaBase1(int master,int slave[],int n)
	{
		if(n==1)
			return (master+slave[0])/2.0;
		if(n%2)
		{
			int a = slave[n/2-1], b=slave[n/2], c = slave[n/2+1];
			if(master<=a)
			{
				return double(a+b)/2;
			}
			else if(master>=c)
			{
				return double(b+c)/2;
			}
			else
				return double(b+master)/2;
		}
		else
		{
			int a = slave[n/2],b = slave[n/2-1];
			if(master>=a)
				return a;
			else if(master<=b)
				return b;
			else
				return master;
		}
	}

	double getMedianBase2(int master[],int slave[],int n)
	{
		if(n==2)
		{
			if(master[1]<=slave[0])
				return (slave[0]+master[1])/2.0;
			else if(master[1]<=slave[1])
				return (master[1]+max(slave[0],master[0]))/2.0;
			else 
				return (slave[1]+max(slave[0],master[0]))/2.0;
		}
		//size of master is 2		
		if(n%2)
		{
			int a = slave[n/2-1],b = slave[n/2],c = slave[n/2+1];
			if(master[1]<=a)
				return a;
			else if(master[1]<=b)
				return master[1];
			else if(master[1]<=c)
				return max(master[0],b);
			else
				return (master[0]>=c)?c:max(master[0],b);
		}
		else
		{
			int a = slave[n/2-2], b = slave[n/2-1], c=slave[n/2], d = slave[n/2+1];
			if(master[1]<=a)
				return (a+b)/2.0;
			else if(master[1]<=b)
				return (master[1]+b)/2.0;
			else if(master[1]<=c)
				return (master[1]+max(master[0],b))/2.0;
			else if(master[1]<=d)
				return (c+max(master[0],b))/2.0;
			else if(master[0]>=d)
				return (c+d)/2.0;
			else if(master[0]>=b)
				return (c+master[0])/2.0;
			else
				return (c+b)/2.0;
				
		}
	}
};
#endif